#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:

    bool vis1[10][10];
    bool vis2[10][10];
    bool vis3[3][3][10];

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.')
                    vis1[i][board[i][j] - '0'] = true;
                if (board[j][i] != '.')
                    vis2[i][board[j][i] - '0'] = true;
                if (board[i][j] != '.')
                    vis3[i / 3][j / 3][board[i][j] - '0'] = true;
            }
        }
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char>>& board, int posi, int posj)
    {
        while (posi < 9 && board[posi][posj] != '.') {
            posj++;
            posi += posj / 9;
            posj %= 9;
        }
        if (posi == 9) return true;
        for (int k = 1; k <= 9; k++) {
            if (!vis1[posi][k] && !vis2[posj][k] && !vis3[posi / 3][posj / 3][k]) {
                vis1[posi][k] = true;
                vis2[posj][k] = true;
                vis3[posi / 3][posj / 3][k] = true;
                board[posi][posj] = k + '0';
                if (dfs(board, posi, posj)) {
                    return true;
                }
                vis1[posi][k] = false;
                vis2[posj][k] = false;
                vis3[posi / 3][posj / 3][k] = false;
                board[posi][posj] = '.';
            }
        }
        return false;
    }
};

class Solution {
public:

    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };

    bool vis[8][8];
    int m, n;

    bool exist(vector<vector<char>>& board, string word) {
        string tmpStr;
        m = board.size();
        n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    vis[i][j] = true;
                    if (dfs(board, word, i, j, 1))
                        return true;
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int x, int y, int count)
    {
        if (count == word.size()) return true;
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy] && board[xx][yy] == word[count]) {
                vis[xx][yy] = true;
                if (dfs(board, word, xx, yy, count + 1)) {
                    return true;
                }
                vis[xx][yy] = false;
            }
        }
        return false;
    }

};

class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };

    bool vis[18][18];
    long long ans;
    int m, n;

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    vis[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    vis[i][j] = false;
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, long long sum)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy] && grid[xx][yy] != 0) {
                vis[xx][yy] = true;
                dfs(grid, xx, yy, sum + grid[xx][yy]);
                vis[xx][yy] = false;
            }
            else ans = max(ans, sum);
        }
    }
};

class Solution {
    int zero_d;
    int m, n;
    int ans;
    int ex, ey;
    bool vis[21][21];
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int bx, by;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0)
                    zero_d++;
                else if (grid[i][j] == 1) {
                    bx = i;
                    by = j;
                }
                // else if(grid[i][j] == 2){
                //     ex = i;
                //     ey = j;
                // }
            }
        }
        vis[bx][by] = true;
        // cout << zero_d <<endl;
        dfs(grid, bx, by, 0);
        return ans;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, int zd)
    {
        // cout << zd << endl;
        if (zd - 1 == zero_d) {
            if (grid[x][y] == 2)
                ans++;
            return;
        }
        if (grid[x][y] == 2) return;

        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy] && grid[xx][yy] != -1) {
                vis[xx][yy] = true;
                dfs(grid, xx, yy, zd + 1);
                vis[xx][yy] = false;
            }
        }
    }

};